//== SAGITTARIUS ============================================================================

//== BEGINNING OF CODE ===============================================================

#include "sagittarius/core/SagittariusCore.h"

//SAGITTARIUS headers:
#include "sagittarius/re/reCS.h"
#include "sagittarius/io/io.h"

//#include <stdio.h>
#include <stdlib.h>
//#include <time.h>
#include <string.h>
//#include <time.h>

void re_symMin(LXAlphaType* r, LXAlphaType x, LXAlphaType y) {
    if(LX_CMPALPHA_LTE(x, y))
        LX_ALPHA_SET(*r, x);
    else
        LX_ALPHA_SET(*r, y);
}

void re_symMax(LXAlphaType* r, LXAlphaType x, LXAlphaType y) {
    if(LX_CMPALPHA_LT(y, x))
        LX_ALPHA_SET(*r, x);
    else
        LX_ALPHA_SET(*r, y);
}

/// re_rangeIsValid
int re_rangeIsValid(RECS_Range r) {
    if(!LX_CMPALPHA_EQ_SPC(r.l, CONST_RE_NULL))
        return 1;
    else
        return 0;
}

/// re_constructRange
RECS_Range re_constructRange(LXAlphaType l, LXAlphaType u) {
    RECS_Range r;
    AT(LX_CMPALPHA_LTE(l, u));
    
    LX_FORCE_INIT(r.l);
    LX_FORCE_INIT(r.u);
    LX_ALPHA_SET(r.l, l);
    LX_ALPHA_SET(r.u, u);
    return r;
}

/// re_constructRangeFixed
RECS_Range re_constructRangeFixed(LXFixedType l, LXFixedType u) {
    RECS_Range r;
    AT(l <= u);
    
    LX_FORCE_INIT(r.l);
    LX_FORCE_INIT(r.u);
    LX_ALPHA_SET_SPC(r.l, l);
    LX_ALPHA_SET_SPC(r.u, u);
    return r;
}

/// re_constructRangeS
RECS_Range re_constructRangeS(LXAlphaType x) {
    return re_constructRange(x, x);
}

/// re_copyRange
/* void re_copyRange(RECS_Range* res, RECS_Range r) {
    
}*/

/// re_deleteRange
void re_deleteRange(RECS_Range* r) {
#if SAGITTARIUS_LXALPHA_USE_GMP
    sg_bignum_clear(&r->u);
    sg_bignum_clear(&r->l);
#endif
}

/// re_compareRange
int re_compareRanges(RECS_Range r, RECS_Range s) {
    if(LX_CMPALPHA_LTE(r.l, s.l) && LX_CMPALPHA_LTE(r.u, s.u))
        return 1;
    else
        return 0;
}

/// re_rangeDiam
void re_rangeDiam(LXAlphaType* res, RECS_Range r) {
    LX_ALPHA_SUB(*res, r.u, r.l);
    LX_ALPHA_INC(*res);
}

/// re_rangeContains
int re_rangeContains(RECS_Range r, LXAlphaType x) {
    /*SG_WRITE(2, "  Range contains: ");
    re_writeRange(2, r);
    SG_WRITE(2, "\n");*/
    if(LX_CMPALPHA_LTE(r.l, x) && LX_CMPALPHA_LTE(x, r.u))
        return 1;
    else
        return 0;
}

/// re_CSsample
LXAlphaType re_CSsample(RE_CharSet* cs) {
    AT(!re_CSisEmpty(cs), "Can't sample an empty CS");
    return cs->ranges[0].l;
}

/// re_CScount
void re_CScount(LXAlphaType* count, RE_CharSet* cs) {
    uint32 i;
    //LXAlphaType count;
    LXAlphaType range; //bounds on range
    
    //LX_FORCE_INIT(count);
    LX_FORCE_INIT(range);
    LX_ALPHA_SET_SPC(*count, 0);
    
    for(i=0; i<cs->n; ++i) {
        re_rangeDiam(&range, cs->ranges[i]);
        /*SG_WRITE(1, "re_CScount Number of characters in range: ");
        LX_ALPHA_WRITEINT(1, range);
        SG_WRITE(1, "\n");*/
        LX_ALPHA_ADD(*count, *count, range);
        /*SG_WRITE(1, "re_CScount *count: ");
        LX_ALPHA_WRITEINT(1, *count);
        SG_WRITE(1, "\n");*/
    }
    
    LX_ALPHA_CLEAR(range);
}

/// re_writeAlpha
void re_writeAlpha(int fd, LXAlphaType x) {
    if(LX_CMPALPHA_EQ_SPC(x, CONST_RE_NULL)) {
        sg_writeUChar(fd, 0x2205);
        return;
    }
    if(LX_CMPALPHA_EQ_SPC(x, CONST_RE_EMPTY_STR)) {
        SG_WRITE(2, "--");
        sg_writeUChar(fd, 0x1D700);
        SG_WRITE(2, "--");
        return;
    }
    if(LX_CMPALPHA_EQ_SPC(x, CONST_RE_ALPHAMAX)) {
        sg_writeUChar(fd, 0x221E);
        return;
    }
    if(LX_CMPALPHA_EQ_SPC(x, CONST_RE_MAX)) {
        sg_writeCStr(fd, "MAX");
        return;
    }
    if(LX_CMPALPHA_EQ_SPC(x, 0x7f)) {
        sg_writeCStr(fd, "DEL"); //the only non-printable ASCII char above 0x20
        return;
    }
    if(LX_CMPALPHA_GTE_SPC(x, 0x20) && !LX_CMPALPHA_EQ_SPC(x, 0x7f)) {
        LX_WRITE_BUFL(fd, &x, 1);
        return;
    }
    sg_writeUInt64(fd, LX_GET_FIXED_VALUE(x));
}

/// re_printRange
/*int re_printRange(RECS_Range r) {
    LXAlphaType b[2];
    b[1] = UC_Null;
    if(!LX_CMPALPHA_EQ(r.l, r.u)) {
        b[0] = r.l;
        printUnicodeBuf(b);
        printf("-");
        b[0] = r.u;
        printUnicodeBuf(b);
    } else {
        b[0] = r.l;
        printUnicodeBuf(b);
    }
    return 0;
}*/

/// re_printRanges
/*int re_printRanges(RECS_Range* r, int n) {
    uint32 i;
    
    printf("Ranges{");
    for(i=0; i<n; ++i) {
        re_printRange(r[i]);
        if(i<n-1)
            printf(",");
    }
    printf("}");
    return 0;
}*/

/// re_writeRange
int re_writeRange(int fd, RECS_Range r) {
    /*sg_writeUInt(fd, r.l);
    SG_WRITE(fd, "-");
    sg_writeUInt(fd, r.u);
    return 0;*/
    if(!LX_CMPALPHA_EQ(r.l, r.u)) {
        re_writeAlpha(fd, r.l);
        SG_WRITE(fd, "-");
        re_writeAlpha(fd, r.u);
    } else {
        re_writeAlpha(fd, r.l);
    }
    return 0;
}

/// re_printRanges
int re_writeRanges(int fd, RECS_Range* r, int n) {
    uint32 i;
    
    SG_WRITE(fd, "Ranges{");
    for(i=0; i<n; ++i) {
        re_writeRange(1, r[i]);
        if(i<n-1)
            printf(",");
    }
    SG_WRITE(fd, "}");
    return 0;
}

/*
/// re_rangeMin
const RECS_Range* re_rangeMin(const RECS_Range* p, const RECS_Range* q) {
    if(p->l <= q->l)
        return p;
    else
        return q;
}

/// re_sortRanges
RE_RangePair re_sortRanges(const RECS_Range* p, const RECS_Range* q) {
    RE_RangePair rs;
    if(p->l <= q->l) {
        rs.p = p;
        rs.q = q;
    } else {
        rs.p = q;
        rs.q = p;
    }
    return rs;
}*/

/// re_rangesIntersect
int re_rangesIntersect(RECS_Range p, RECS_Range q) {
    if(LX_CMPALPHA_LT(p.u, q.l) || LX_CMPALPHA_LT(q.u, p.l))
        return 0;
    else
        return 1;
}

/// re_rangesContact
int re_rangesContact(RECS_Range p, RECS_Range q) {
    int val;
    LXAlphaType pu,qu;
    
    LX_INIT_SET(pu, p.u);
    LX_INIT_SET(qu, q.u);
    LX_ALPHA_INC(pu);
    LX_ALPHA_INC(qu);
    if(LX_CMPALPHA_LT(pu, q.l) || LX_CMPALPHA_LT(qu, p.l))
        val = 0;
    else
        val = 1;
    LX_ALPHA_CLEAR(pu);
    LX_ALPHA_CLEAR(qu);
    
    return val;
}

/// re_intersectRanges
void re_intersectRanges(RECS_Range* r, RECS_Range p, RECS_Range q) {
    /*LXAlphaType min, max;
    LX_FORCE_INIT(min);
    LX_FORCE_INIT(max);
    
    if(!re_rangesIntersect(p,q))
        return re_constructRangeFixed(CONST_RE_NULL, CONST_RE_NULL); //intersection is null
    //otherwise, the intersection is non-empty
    //range will begin at max(q.l, p.l) and end at min(q.u, p.u)
    re_symMax(&min, p.l, q.l);
    re_symMin(&max, p.u, q.u);
    return re_constructRange(min, max);*/
    if(!re_rangesIntersect(p,q)) {
        LX_ALPHA_SET_SPC(r->l, CONST_RE_NULL);
        LX_ALPHA_SET_SPC(r->u, CONST_RE_NULL);
    } else {
        re_symMax(&r->l, p.l, q.l);
        re_symMin(&r->u, p.u, q.u);
    }
}

/// re_uniteRanges
void re_uniteRanges(RECS_Range* r, RECS_Range p, RECS_Range q) {
    /*LXAlphaType min, max;
    LX_FORCE_INIT(min);
    LX_FORCE_INIT(max);*/
    
    //does not check for intersection
    re_symMin(&r->l, p.l, q.l);
    re_symMax(&r->u, p.u, q.u);
    //return re_constructRange(min, max);
}

//-- Set Functions --

/// re_createCSEmpty
RE_CharSet* re_createCSEmpty() {
    RE_CharSet* cs = LX_ALLOC(sizeof(RE_CharSet));
    cs->n = 0;
    return cs;
}

///re_createCSFull
RE_CharSet* re_createCSFull() {
    RE_CharSet* cs = LX_ALLOC(sizeof(RE_CharSet));
#if SAGITTARIUS_LXALPHA_USE_GMP
    cs->ranges[0].l.flg = cs->ranges[0].u.flg = 0;
#endif
    cs->n = 1;
    LX_ALPHA_SET_SPC(cs->ranges[0].l, CONST_RE_ALPHAMIN);
    LX_ALPHA_SET_SPC(cs->ranges[0].u, CONST_RE_ALPHAMAX);
    return cs;
}

/// re_createCSSym
RE_CharSet* re_createCSSym(LXConstAlphaType x) {
    RE_CharSet* cs = LX_ALLOC(sizeof(RE_CharSet));
#if SAGITTARIUS_LXALPHA_USE_GMP
    cs->ranges[0].l.flg = cs->ranges[0].u.flg = 0;
#endif
    LX_ALPHA_SET(cs->ranges[0].l, x);
    LX_ALPHA_SET(cs->ranges[0].u, x);
    cs->n = 1;
    return cs;
}

/// re_createCSFixed
RE_CharSet* re_createCSFixed(LXFixedType x) {
    RE_CharSet* cs = LX_ALLOC(sizeof(RE_CharSet));
#if SAGITTARIUS_LXALPHA_USE_GMP
    cs->ranges[0].l.flg = cs->ranges[0].u.flg = 0;
#endif
    LX_ALPHA_SET_SPC(cs->ranges[0].l, x);
    LX_ALPHA_SET_SPC(cs->ranges[0].u, x);
    cs->n = 1;
    return cs;
}

/// re_createCSNull
RE_CharSet* re_createCSNull() {
    return re_createCSFixed(CONST_RE_NULL);
}

/// re_createCSEmptyStr
RE_CharSet* re_createCSEmptyStr() {
    return re_createCSFixed(CONST_RE_EMPTY_STR);
}

/// re_createCSRange
RE_CharSet* re_createCSRange(LXConstAlphaType l, LXConstAlphaType u) {
    RE_CharSet* cs = LX_ALLOC(sizeof(RE_CharSet));
    cs->ranges[0] = re_constructRange(l, u); //FIXME: allocation?
    cs->n = 1;
    return cs;
}

/// re_copyCS
RE_CharSet* re_copyCS(RE_CharSet* s) {
    /*SG_WRITE(1, "re_copyCS: sizeof(RE_CharSet) = ");
    sg_writeUInt64(1, sizeof(RE_CharSet));
    SG_WRITE(1, ", s->n = ");
    sg_writeUInt64(1, s->n);
    SG_WRITE(1, ", sizeof(RECS_Range) = ");
    sg_writeUInt64(1, sizeof(RECS_Range));
    SG_WRITE(1, "\n");*/
    size_t bytes=sizeof(RE_CharSet) + (s->n?(s->n-1):0)*sizeof(RECS_Range);
    RE_CharSet *r = LX_ALLOC(bytes);
    AN(r);
#ifdef LX_ALPHA_DO_PERVALUE
    r->n = s->n;
    { uint32 i;
    for(i=0;i<s->n; ++i) {
        LX_FORCE_INIT(r->ranges[i].l);
        LX_FORCE_INIT(r->ranges[i].u);
        LX_ALPHA_SET(r->ranges[i].l, s->ranges[i].l);
        LX_ALPHA_SET(r->ranges[i].u, s->ranges[i].u);
    }}
#else
    memcpy(r, s, bytes);
#endif
    return r;
}

/// re_CSAddRange
RE_CharSet* re_CSAddRange(RECS_Range r, RE_CharSet* s) {
#ifdef LX_ALPHA_DO_PERVALUE
    uint32 i;
#endif
    RE_CharSet* res;
    uint32 n = s->n+1;
    AT(n >= 1);
    res = LX_ALLOC(sizeof(RE_CharSet) + (n-1)*sizeof(RECS_Range));
    /*SG_WRITE(1, "Add range at ");
    sg_writePtr(1, res);
    SG_WRITE(1, ": ");
    re_writeRange(1, r);
    SG_WRITE(1, "\n");*/
#ifdef LX_ALPHA_DO_PERVALUE
    if(n > 1) {
        for(i=0;i<n-1; ++i) {
            LX_FORCE_INIT_RANGE(res->ranges[i]);
            LX_SET_RANGE(res->ranges[i], s->ranges[i]);
        }
    }
#else
    if(n > 1)
        AN( memcpy(res->ranges, s->ranges, (n-1)*sizeof(RECS_Range)) );
#endif
    res->n = n;
    LX_FORCE_INIT_RANGE(res->ranges[n-1]);
    LX_SET_RANGE(res->ranges[n-1], r);
    return res;
}

/// re_CSMix
//Adds multiple ranges without checking for overlap
RE_CharSet* re_CSMix(RE_CharSet* r, RE_CharSet* s) {
#ifdef LX_ALPHA_DO_PERVALUE
    uint32 i;
#endif
    RE_CharSet* q;
    uint32 n = r->n+s->n;
    if(n < 1)
        return re_createCSEmpty();
    q = LX_ALLOC(sizeof(RE_CharSet) + (n-1)*sizeof(RECS_Range));
#ifdef LX_ALPHA_DO_PERVALUE
    if(r->n >= 1)
        for(i=0;i<r->n; ++i) {
            LX_FORCE_INIT(q->ranges[i].l);
            LX_FORCE_INIT(q->ranges[i].u);
            LX_SET_RANGE(q->ranges[i], r->ranges[i]);
        }
    if(s->n >= 1)
        for(i=0;i<s->n; ++i) {
            LX_FORCE_INIT(q->ranges[i+r->n].l);
            LX_FORCE_INIT(q->ranges[i+r->n].u);
            LX_SET_RANGE(q->ranges[i+r->n], s->ranges[i]);
        }
#else
    if(r->n >= 1)
        AN( memcpy(q->ranges, r->ranges, r->n*sizeof(RECS_Range)) );
    if(s->n >= 1)
        AN( memcpy(q->ranges+r->n, s->ranges, s->n*sizeof(RECS_Range)) );
#endif
    q->n = n;
    return q;
}

/// re_CSComplement
RE_CharSet* re_CSComplement(RE_CharSet* p) {
    uint32 i=0;
    RECS_Range* r;
    RE_CharSet* cs;
    uint32 n=p->n+1;
    LXAlphaType a, b;
    LX_FORCE_INIT(a);
    LX_FORCE_INIT(b);
    /*SG_WRITE(2, "re_CSComplement: ");
    re_writeCS(2, p);
    SG_WRITE(2, "\n");*/
    if(p->n == 0)
        return re_createCSFull();
    if(re_CSisFull(p))
        return re_createCSEmpty();
    if(re_CSisEmptyStr(p) || re_CSisNull(p)) //TODO: implement null as an empty charset
        AN(0, "Invalid charset");
    
    if(LX_CMPALPHA_EQ_SPC(p->ranges[0].l, CONST_RE_ALPHAMIN))
        --n;
    if(LX_CMPALPHA_EQ_SPC(p->ranges[p->n-1].u, CONST_RE_ALPHAMAX))
        --n;
    AT(n > 0);
    
    cs = LX_ALLOC(sizeof(RE_CharSet) + (n-1)*sizeof(RECS_Range));
    cs->n = n;
    
    LX_ALPHA_SET_SPC(a, CONST_RE_ALPHAMIN);
    LX_ALPHA_SET_SPC(b, CONST_RE_ALPHAMIN); //dummy value
    r = &cs->ranges[0];
    while(i<p->n) {
        LX_ALPHA_SET(b, p->ranges[i].l);
        /*#if SAGITTARIUS_LXALPHA_USE_GMP
        if(LX_IS_ALPHAMIN(b)) 
            goto skip; //this isn't really necessary since GMP bignums are signed...
        #endif*/
        LX_ALPHA_DEC(b);
        if(LX_CMPALPHA_LTE(a, b)) //FIXME: should this be < or <=?
            *r = re_constructRange(a, b);
        //skip:
        LX_ALPHA_ADD_SPC(a, p->ranges[i].u, 1);
        ++i;
        ++r;
    }
    LX_ALPHA_SET_SPC(b, CONST_RE_ALPHAMAX);
    /*SG_WRITE(2, "re_CSComplement a = ");
    re_writeAlpha(2, a);
    SG_WRITE(2, ", re_CSComplement b = ");
    re_writeAlpha(2, b);
    SG_WRITE(2, "\n");*/
    if(LX_CMPALPHA_LTE(a, b)) //FIXME: should this be < or <=?
        *r = re_constructRange(a, b);
    
    LX_ALPHA_CLEAR(a);
    LX_ALPHA_CLEAR(b);
    
    return cs;
}

/// re_destroyCS
void re_destroyCS(RE_CharSet* cs) {
#ifdef LX_ALPHA_DO_PERVALUE
    uint32 i;
#endif
    AN(cs);
#ifdef LX_ALPHA_DO_PERVALUE
    for(i=0; i<cs->n; ++i) {
        LX_CLEAR_RANGE(cs->ranges[i]);
    }
#endif
    LX_FREE((void*)cs);
}

/// re_CSisEmpty
int re_CSisEmpty(RE_CharSet* cs) {
    if(cs->n == 0)
        return 1;
    else
        return 0;
}

/// re_CSisSymbol
int re_CSisSymbol(RE_CharSet* cs) {
    if(cs->n == 1 && LX_CMPALPHA_EQ(cs->ranges[0].l, cs->ranges[0].u))
        return 1;
    else
        return 0;
}

/// re_CSisNull
int re_CSisNull(RE_CharSet* cs) {
    if(re_CSisSymbol(cs) && LX_CMPALPHA_EQ_SPC(cs->ranges[0].l, CONST_RE_NULL))
        return 1;
    else
        return 0;
}

/// re_CSisEmptyStr
int re_CSisEmptyStr(RE_CharSet* cs) {
    if(re_CSisSymbol(cs) && LX_CMPALPHA_EQ_SPC(cs->ranges[0].l, CONST_RE_EMPTY_STR))
        return 1;
    else
        return 0;
}

/// re_CSisEmptyStr
int re_CSisSpecial(RE_CharSet* cs) {
    if(re_CSisSymbol(cs)) {
        if(LX_CMPALPHA_EQ_SPC(cs->ranges[0].l, CONST_RE_ALPHAMIN) ||
           LX_CMPALPHA_EQ_SPC(cs->ranges[0].l, CONST_RE_ALPHAMAX) ||
           LX_CMPALPHA_EQ_SPC(cs->ranges[0].l, CONST_RE_EMPTY_STR) ||
           LX_CMPALPHA_EQ_SPC(cs->ranges[0].l, CONST_RE_NULL) ||
           LX_CMPALPHA_EQ_SPC(cs->ranges[0].l, CONST_RE_MAX))
            return 1;
    }
    return 0;
}

/// re_SCisFull
int re_CSisFull(RE_CharSet* cs) {
    if(cs->n == 1 && LX_CMPALPHA_EQ_SPC(cs->ranges[0].l, CONST_RE_ALPHAMIN) && LX_CMPALPHA_EQ_SPC(cs->ranges[0].u, CONST_RE_ALPHAMAX))
        return 1;
    else
        return 0;
}

/// re_CSgetSymbol
LXAlphaType re_CSgetSymbol(RE_CharSet* cs) {
    AT(re_CSisSymbol(cs), "Expected single symbol");
    return cs->ranges[0].l;
}

/// re_CSSymComp
int re_CSSymComp(RE_CharSet* cs, LXAlphaType x) {
    AN(cs);
    if(cs->n == 1)
        if(LX_CMPALPHA_EQ(x, cs->ranges[0].l) && LX_CMPALPHA_EQ(x, cs->ranges[0].u))
            return 1;
    return 0;
}

typedef struct {
    RE_CharSet* cs;
    uint32 rng;
    int beg;
} re_compareState;

/// re_compareCS
int re_compareCS(RE_CharSet* r, RE_CharSet* s) {
    uint32 i=0;
    re_compareState c1, c2;
	c1.cs = r; c1.rng = 0;
	c2.cs = s; c2.rng = 0;
   /*SG_WRITE(2, "re_compareCS: ");
    re_writeCS(2, r);
    SG_WRITE(2, ", ");
    re_writeCS(2, s);
    SG_WRITE(2, "\n");*/
    //The order relation on charsets can be confusing
    //For example, {b}<{a}
    //This is because the order on charsets is the dictionary order on
    //the cart product of include relations {1 if symbol a is in CS, 0 otherwise}
    //so {b} ~ {0,1}, {a} ~ {1,0}
    //This makes it easier to see why {b}<{a}
    //Continuing, if there were a {c}, it would be {0,0,1} etc.
    while(1) {
        if(r->n == i) {
            if(s->n == i)
                return RECS_COMPARE_EQ;
            else
                return RECS_COMPARE_LT;
        } else if(s->n == i)
            return RECS_COMPARE_GT;
        
        if(LX_CMPALPHA_LT(c1.cs->ranges[i].l, c2.cs->ranges[i].l))
            return RECS_COMPARE_GT;
        else if(LX_CMPALPHA_GT(c1.cs->ranges[i].l, c2.cs->ranges[i].l))
            return RECS_COMPARE_LT;
        
        if(LX_CMPALPHA_LT(c1.cs->ranges[i].u, c2.cs->ranges[i].u))
            return RECS_COMPARE_LT;
        else if(LX_CMPALPHA_LT(c1.cs->ranges[i].u, c2.cs->ranges[i].u))
            return RECS_COMPARE_GT;
        ++i;
    }
}

/// re_CSeq
int re_CSeq(RE_CharSet* r, RE_CharSet* s) {
    if(re_compareCS(r,s) == RECS_COMPARE_EQ)
        return 1;
    else
        return 0;
}

/// re_CSlb
void re_CSlb(LXAlphaType* r, RE_CharSet* p) {
    int32 i=0;
    AT(p->n > 0, "It is an error to call re_CSlb for an empty set");
    LX_ALPHA_SET(*r, p->ranges[0].l);
    for(; i<p->n; ++i)
        if(LX_CMPALPHA_LT(p->ranges[i].l, *r))
            LX_ALPHA_SET(*r, p->ranges[i].l);
}

/// re_CSlb
void re_CSub(LXAlphaType* r, RE_CharSet* p) {
    int32 i=0;
    AT(p->n > 0, "It is an error to call re_CSub for an empty set");
    LX_ALPHA_SET(*r, p->ranges[0].u);
    for(; i<p->n; ++i)
        if(LX_CMPALPHA_GT(p->ranges[i].u, *r))
            LX_ALPHA_SET(*r, p->ranges[i].u);
}

/// re_printCS
/*int re_printCS(RE_CharSet* s) {
    uint32 i;
    
    printf("CS{");
    for(i=0; i<s->n; ++i) {
        re_printRange(s->ranges[i]);
        if(i<s->n-1)
            printf(",");
    }
    printf("}");
    return 0;
}*/

/// re_printCS
void re_writeCS(int fd, RE_CharSet* s) {
    uint32 i;
    
    if(re_CSisSymbol(s)) {
        re_writeAlpha(fd, re_CSgetSymbol(s));
        return;
    }
    SG_WRITE(fd, "CS{");
    for(i=0; i<s->n; ++i) {
        re_writeRange(fd, s->ranges[i]);
        if(i<s->n-1)
            SG_WRITE(fd, ",");
    }
    SG_WRITE(fd, "}");
}

/// re_CSContains
int re_CSContains(RE_CharSet* cs, LXAlphaType x) {
    uint32 i;
    for(i=0; i<cs->n; ++i) {
        if(re_rangeContains(cs->ranges[i], x))
            return 1;
    }
    return 0;
}

/// re_intersectRangeSet
#if LX_USE_POOLALLOC
    RE_CharSet* re_intersectRangeSet(RECS_Range r, RE_CharSet* s) {
        /*SG_WRITE(1, "re_intersectRangeSet: ");
        re_writeRange(1, r);
        SG_WRITE(1, " ∩ ");
        re_writeCS(1, s);
        SG_WRITE(1, "\n");*/
        uint32 i;
        RE_CharSet* q = re_createCSEmpty();
        RECS_Range newr;
		{
			LX_PUSH_SAVE_SEG(&lx_tmpseg); //do new allocations in tmp
        
			AT(s->n >= 1);
			for(i=0; i<s->n; ++i) {
				re_intersectRanges(&newr, r, s->ranges[i]);
				if(re_rangeIsValid(newr))
					q = re_CSAddRange(newr, q);
			}
			//copy result to level above
			LX_PUSH_SEG(LX_SEG_GET(1));
				q = re_copyCS(q); //nice thing: we don't even have to free the old q since this is a temp segment
			LX_POP_SEG();
			LX_POP_RESTORE_SEG();
		}
        /*SG_WRITE(1, "re_intersectRangeSet result: ");
        re_writeCS(1, q);
        SG_WRITE(1, "\n");*/
        return q;
    }
#else
    RE_CharSet* re_intersectRangeSet(RECS_Range r, RE_CharSet* s) {
        uint32 i;
        RE_CharSet* q = re_createCSEmpty();
        RE_CharSet* tmp;
        RECS_Range newr;
        LX_FORCE_INIT_RANGE(newr);
        
        AT(s->n >= 1);
        for(i=0; i<s->n; ++i) {
            re_intersectRanges(&newr, r, s->ranges[i]);
            if(re_rangeIsValid(newr)) {
                tmp = q;
                q = re_CSAddRange(newr, q);
                re_destroyCS(tmp);
            }
        }
        LX_CLEAR_RANGE(newr);
        return q;
    }
#endif

/// re_uniteRangeSet
#if LX_USE_POOLALLOC
//DANGER: check that this works for a union c
    RE_CharSet* re_uniteRangeSet(RECS_Range r, RE_CharSet* s) {
        uint32 i;
        RE_CharSet* q = re_createCSEmpty();
        RECS_Range newr = r;
        LX_PUSH_SAVE_SEG(&lx_tmpseg); //do new allocations in tmp
        
        for(i=0; i<s->n; ++i) {
            //DONE: case where intervals touch but do not intersect
            if(re_rangesContact(newr,s->ranges[i]))
                re_uniteRanges(&newr, newr, s->ranges[i]);
            else
                q = re_CSAddRange(s->ranges[i], q);
        }
        //put result in level above
        LX_PUSH_SEG(LX_SEG_GET(1));
            q = re_CSAddRange(newr, q);
        LX_POP_SEG();
        LX_POP_RESTORE_SEG();
        return q;
    }
#else
    RE_CharSet* re_uniteRangeSet(RECS_Range r, RE_CharSet* s) {
        uint32 i;
        RE_CharSet* q = re_createCSEmpty();
        RE_CharSet* tmp;
        RECS_Range newr;
        LX_FORCE_INIT_RANGE(newr);
        LX_SET_RANGE(newr, r);
        
        //TODO: since the elements in s are assumed to be disjoint 
        //xxxand sortedxxx (not necessarily sorted), this can be sped up
        for(i=0; i<s->n; ++i) {
            //DONE: case where intervals touch but do not intersect
            if(re_rangesContact(newr,s->ranges[i]))
                re_uniteRanges(&newr, newr, s->ranges[i]);
            else {
                tmp = q;
                q = re_CSAddRange(s->ranges[i], q);
                re_destroyCS(tmp);
            }
        }
        tmp = q;
        q = re_CSAddRange(newr, q);
        re_destroyCS(tmp);
        LX_CLEAR_RANGE(newr);
        return q;
    }
#endif

/// re_CSUnion
#if LX_USE_POOLALLOC
//complexity: p->n*q->n
RE_CharSet* re_CSUnion(RE_CharSet* p, RE_CharSet* q) {
    uint32 i;
    RE_CharSet* t;
    
    AT(p->n >= 0 && q->n >= 0);
    if(p->n == 0)
        return q;
    
	{
		LX_PUSH_SAVE_SEG(&lx_tmpseg); //do new allocations in tmp
    
		t = re_uniteRangeSet(p->ranges[0], q);
		for(i=1; i<p->n; ++i) {
			if(i == p->n-1) {
				LX_PUSH_SEG(LX_SEG_GET(1)); //put result in level above
				t = re_uniteRangeSet(p->ranges[i], t);
				LX_POP_SEG();
			} else
				t = re_uniteRangeSet(p->ranges[i], t);
		}
		//FIXED 08/13 (was doing alloc for return val in tmp)
		//put result in level above
		LX_PUSH_SEG(LX_SEG_GET(1));
			t = re_copyCS(t);
		LX_POP_SEG();
		LX_POP_RESTORE_SEG();
	}
    return t;
}
#else
//complexity: p->n*q->n
RE_CharSet* re_CSUnion(RE_CharSet* p, RE_CharSet* q) {
    uint32 i;
    
    //DONE: use a pool to do allocation (above)
    AT(p->n >= 0 && q->n >= 0);
    if(p->n == 0)
        return re_copyCS(q);
    RE_CharSet* t = re_uniteRangeSet(p->ranges[0], q);
    /*SG_WRITE(1, "re_uniteRangeSet initial t = ");
    re_writeCS(1, t);
    SG_WRITE(1, "\n");*/
    RE_CharSet* u;
    for(i=1; i<p->n; ++i) {
        u = re_uniteRangeSet(p->ranges[i], t);
        /*SG_WRITE(1, "re_uniteRangeSet = ");
        re_writeCS(1, u);
        SG_WRITE(1, "\n");*/
        re_destroyCS(t);
        t = u;
    }
    return t;
}
#endif

/// re_CSIntersect
#if LX_USE_POOLALLOC
//complexity: a lot
RE_CharSet* re_CSIntersect(RE_CharSet* p, RE_CharSet* q) {
    /*re_writeCS(2, p);
    SG_WRITE(2, " ∩ ");
    re_writeCS(2, q);
    SG_WRITE(2, "\n");*/
    uint32 i;
    RE_CharSet *t, *u;
    LX_PUSH_SAVE_SEG(&lx_tmpseg); //do new allocations in tmp
    
    t = re_createCSEmpty();
    AT(p->n > 0 && q->n > 0);
    for(i=0; i<p->n; ++i) {
        u = re_intersectRangeSet(p->ranges[i], q);
        if(!re_CSisEmpty(u))
            t = re_CSMix(u, t);
    }
    //copy result to level above
    LX_PUSH_SEG(LX_SEG_GET(1));
        t = re_copyCS(t);
    LX_POP_SEG();
    LX_POP_RESTORE_SEG();
    /*SG_WRITE(2, "re_CSIntersect: ");
    re_writeCS(2, t);
    SG_WRITE(2, "\n");*/
    return t;
}
#else
//complexity: a lot
RE_CharSet* re_CSIntersect(RE_CharSet* p, RE_CharSet* q) {
    /*re_writeCS(2, p);
    SG_WRITE(2, " ∩ ");
    re_writeCS(2, q);
    SG_WRITE(2, "\n");*/
    uint32 i;
    RE_CharSet *t=re_createCSEmpty(), *u, *v;
    
    //DONE: use a pool to do allocation
    AT(p->n > 0 && q->n > 0);
    for(i=0; i<p->n; ++i) {
        u = re_intersectRangeSet(p->ranges[i], q);
        if(!re_CSisEmpty(u)) {
            v = re_CSMix(u, t);
            re_destroyCS(t);
            t = v;
        }
        re_destroyCS(u);
    }
    /*SG_WRITE(2, "re_CSIntersect: ");
    re_writeCS(2, t);
    SG_WRITE(2, "\n");*/
    return t;
}
#endif

int re_CSPart(RECS_Range* r, int n, int p) {
    uint32 i;
#if !SAGITTARIUS_LXALPHA_USE_GMP
    RECS_Range tmp;
#endif
    
    //printf("re_CSPart, n = %d, p = %d\n", n, p);
    
    AT(n > 0);
    //GMP has a macro for this
    //GCC: check out int32_t __builtin_bswap32
#if SAGITTARIUS_LXALPHA_USE_GMP
    #define SWAP(x, y) mpz_swap(x.l.v, y.l.v); mpz_swap(x.u.v, y.u.v)
#else
    #define SWAP(x,y) tmp = x; x = y; y = tmp
#endif
    //move pivot to the end
    SWAP(r[n-1],r[p]);
    //int s=0;
    p=0;
    for(i=0; i<n-1; ++i) {
        if(LX_CMPALPHA_LT(r[i].l, r[n-1].l)) {
            SWAP(r[p], r[i]);
            ++p;
        }
    }
    //move pivot to position
    SWAP(r[n-1],r[p]);
    #undef SWAP
    return p; //pivot index
}

//TODO: adapt to bignum macros (nothing to do?)
int re_CS_qsort(RECS_Range* r, int n, int p) {
    /*printf("re_CS_qsort, n = %d\n  ", n);
    re_printRanges(r, n);
    printf("\n");*/
    //int p = rand() % n;
    p = re_CSPart(r, n, p);
    /*printf("    ");
    re_printRanges(r, n);
    printf("\n");*/
    if(p > 1)
        re_CS_qsort(r, p, rand() % p);
    if(n-(p+1) > 1)
        re_CS_qsort(&r[p+1], n-(p+1), rand() % (n-(p+1)));
    return 0;
}

//TODO: adapt to bignum macros (nothing to do?)
int re_CSSortInPlace(RE_CharSet* s) {
    //printf("re_CSSortInPlace\n");
    if(s->n <= 1)
        return 1;
    re_CS_qsort(s->ranges, s->n, rand() % s->n);
    return 0;
}

/// re_CSSort
RE_CharSet* re_CSSort(RE_CharSet* s) {
    //assumes the set is disjoint, like most of these functions
    RE_CharSet* q = re_copyCS(s);
    re_CSSortInPlace(q);
    return q;
}

/// re_CSIStart
RE_CharSetIter re_CSIStart(RE_CharSet* s) {
    RE_CharSetIter i;
	i.i = NULL;
	i.stop = NULL;
    if(s->n < 1)
        return i;
    i.i = s->ranges;
    i.stop = i.i + s->n;
    if(i.i == i.stop) {
        i.i = NULL;
        return i;
    }
    LX_FORCE_INIT(i.a);
    LX_ALPHA_SET(i.a, i.i->l);
    return i;
}

/// re_CSINext
int re_CSINext(RE_CharSetIter* i) {
    if(LX_CMPALPHA_EQ(RE_CSITER_GET(*i), i->i->u)) {
        ++i->i;
        if(i->i == i->stop) {
            i->i = NULL;
            return 0;
        } else {
            LX_ALPHA_SET(i->a, i->i->l);
            return 1;
        }
    } else {
        //just increment alpha
        LX_ALPHA_INC(i->a);
        return 1;
    }
}

/// re_CSIValid
int re_CSIValid(RE_CharSetIter* i) {
    if(i->i)
        return 1;
    else
        return 0;
}
